#include<iostream>
#include<vector>
#include<deque>
using namespace std;
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> queue;
        int n = nums.size();
        vector<int> ret;
        for(int i = 0;i<n;i++)
        {
            //入队列
            while(!queue.empty()&&nums[queue.back()]<=nums[i])
            {
                //当现在插入的这个数字比最后一个数字要大，那么这个数字可能是之后的最大值，直到
                //一直保持queueu中的单调递增属性
                queue.pop_back();
            }
            queue.push_back(i);
            //出队列
            if(i-queue.front()>=k)
            {
                //说明在队列中的元素大于了滑动窗口能够储存的元素
                queue.pop_front();//删除头部元素，这里因为会对每一个加入的元素都进行判断
                //所以当刚好大于k的时候就会被删除，所以不需要使用while循环
            }
            if(i>=k-1)
            {
                //说明滑动窗口中的元素已经满足了条件
                ret.push_back(nums[queue.front()]);
                //ret:3
            }
        }
        return ret;
    }
};